package leetcode_81_100;

public class numTrees_96 {
    /**
     * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种
     * 返回满足题意的二叉搜索树的种数。
     * @param n 1 <= n <= 19
     * @return
     */
    public int numTrees(int n) {
        /**
         * 参考95题写的递归解法
         * 好慢，2415ms
         */
        if(n==1)
            return 1;
        return num(1,n);
    }
    int num(int start,int end){
        int num=0; //该层递归的种类数量
        if(start==end || end<start) //当左边是null，或者只有1位数字，都可以是一种二叉树
            return 1;
        for(int i=start;i<=end;i++){
            int left=num(start,i-1);
            int right=num(i+1,end);
            //两两组合
            num+=left*right;
        }
        return num;
    }

    /**
     * 动态规划处理
     * @param n
     * @return
     */
    public int numTrees2(int n) {
        /**
         * 类似95题中的递归思路
         * 假设 n 个节点存在二叉排序树的个数是 G (n)
         *  f(i) 为以 i 为根的二叉搜索树的个数，则
         * G(n)=f(1)+f(2)+f(3)+f(4)+...+f(n)
         * 当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i，则
         * f(i)=G(i−1)∗G(n−i)
         */
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i < n + 1; i++)
            for(int j = 1; j < i + 1; j++)
                dp[i] += dp[j-1] * dp[i-j];

        return dp[n];
    }
}
